Hardshad Numbers#

Try me#

Open In ColabBinder

Problem Definition#

Harshad numbers or Niven numbers are integer numbers which are divisible by the sum of its digits in a given base. For instance, 12 is a Harshad number in base 10 because it is divisible by (1 + 2) 3, and 20 is a Harshad number because it is divisible by (2 + 0) 2. However, 15 is not a Harshad number in base 10 because it is not divisible by (1+5) 6. In general, an integer number \(X\) can be expressed in a given base \(n\) as:

\[X = \sum_{i=0}^{m-1}{a_i*n^i}\]

where \(m\) is the number of digits and (\(a_0, a_1, a_2, ..., a_{m-1}\)) are the digits of the integer number. \(X\) is a Harshad number in base n if and only if:

\[X \mod \sum_{i=0}^{m-1}{a_i0} = 0\]

That is, the remainder after integer division of \(X\) by the sum of its digits is 0. You can read everything about Harshad numbers here.

Write a function that tests if an integer number passed as argument is a Harshad number in base 10 (that is, it returns True if the number can be divided by the sum of its digits). Can you modify the function so that it takes a second parameter with the base for which you want to make the test?

Solution#

The first solution first converts the number to a string and then converts each digit to an integer, to sum the digits one by one in a variable, and then find if the modulo of the number by the sum of its digits is zero:

[ ]:

x = int(input("Enter a number to know if its a Harshad number: "))
# let´s convert it to a string
x_str = str(x)
sum_digits = 0
for digit in x_str:
    sum_digits += int(digit)


if x % sum_digits == 0:
    print(f"{x} is a Harshad number")
else:
    print(f"{x} is not a Harshad number")

This strategy is very Pythonic, compact and elegant, but it cannot be easily generalized to an arbitrary base. However, the following strategy can be applied to any base:

[2]:

x = int(input("Enter a number to know if its a Harshad number: "))
n = int(input("Enter the base: "))
i = 0
sum_digits = 0
while x / (n**i) > 1:
    sum_digits += (x // (n**i)) % n
    i += 1

if x % sum_digits == 0:
    print(f"{x} is a Harshad number in base {n}")
else:
    print(f"{x} is not a Harshad number in base {n}")



6 is a Harshad number in base 2

In this solution, we use a while loop where the stop condition is that the division \(frac{x}base^i}\) is greater than 1. \(i\) is initialized at zero and increased by 1 in each repetition loop. This stop condition ensures that the while loop is stopped when \(i\) is exactly \(m\): the number of digits of %x% in base \(n\) that are non-zero. Then, for every value of \(i\), we calculate the digit as:

\[a_i = (x // n^i) \mod n\]

The left operand of the modulo function is the integer division of x by \(n^i\), which can be any integer number, then we perform the modulo operator to ensure that the number is between 0 and n-1. Let us see an example with n = 10, and x = 133

i

n**i

x/n**i

x // n**i

x // n**i % n

sum_digits

0

1

133

133

3

3

1

10

13.3

13

3

6

2

100

1.33

1

1

7

Finally, we check if the number is a Harshad number by checking if the modulo of the number by the sum of its digits is zero.

Analysis Questions#

These questions are designed to help you better understand the first solution. Try to answer them by yourself before asking for help.

  1. Type Conversion: What is the purpose of converting the number x to a string? How does it help in solving the problem?

  2. Loop Mechanics: How does the loop iterate over each character of x_str? What happens to the variable sum_digits in each iteration?

  3. Edge Cases: Edge cases are extreme cases that can break the program. Can you think of any edge cases for this problem? For instance, what happens if the user enters 0? What happens if the user enters a negative number? What happens if the user enters a non-integer number? How would you modify the program to handle these edge cases?

Here are some questions based on the second solution:

  1. Loop Condition: Explain the condition x / (n**i) > 1. What does this condition ensure, and how does it help in extracting digits of the number in the given base?

  2. Digit Extraction: Describe the process used in the code to extract each digit of x in base n. How is this different from the first solution?

  3. Comparison with First Solution: what are the main differences with respect to the first solution? In what scenarios would this second solution be more appropriate to use, and why?